package SearchSwordOffer;

import ListNodeSecond.SwordOffer.ListNode;

public class MergeKLists {
    /**
     * 剑指 Offer II 078. 合并排序链表
     * 给定一个链表数组，每个链表都已经按升序排列。
     * <p>
     * 请将所有链表合并到一个升序链表中，返回合并后的链表。
     * <p>
     * <p>
     * <p>
     * 示例 1：
     * <p>
     * 输入：lists = [[1,4,5],[1,3,4],[2,6]]
     * 输出：[1,1,2,3,4,4,5,6]
     * 解释：链表数组如下：
     * [
     * 1->4->5,
     * 1->3->4,
     * 2->6
     * ]
     * 将它们合并到一个有序链表中得到。
     * 1->1->2->3->4->4->5->6
     *
     * @param lists
     * @return
     */
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) {
            return null;
        }
        return mergeLists(lists, 0, lists.length);
    }

    private ListNode mergeLists(ListNode[] lists, int start, int end) {
        if (start + 1 == end) {
            return lists[start];
        }
        int mid = (start + end) / 2;
        ListNode listNode = mergeLists(lists, start, mid);
        ListNode listNode1 = mergeLists(lists, mid, end);
        return merge(listNode, listNode1);
    }

    private ListNode merge(ListNode listNode, ListNode listNode1) {
        ListNode yummy = new ListNode(0);
        ListNode temp = yummy;

        while (listNode != null && listNode1 != null) {
            if (listNode.val > listNode1.val) {
                temp.next = listNode1;
                listNode1 = listNode1.next;
            } else {
                temp.next = listNode;
                listNode = listNode.next;
            }
            temp = temp.next;
        }
        if (listNode != null) {
            temp.next = listNode;
        }
        if (listNode1 != null) {
            temp.next = listNode1;
        }
        return yummy.next;
    }
}
